import java.util.ArrayList;
import java.util.List;

public class num22 {
    List<String> list = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if(n == 0) {
            return list;
        }
        //深度遍历查询可能的结果
        dfs("",n,n);
        return list;
    }

    private void dfs(String s, int left, int right) {
        if(left == 0 && right == 0) {
            list.add(s);
            return;
        }
        //左边剩余的大于右边，证明右括号用的多----》 ）（）,需要剪枝
        if(left > right) {
            return;
        }
        if(left > 0) {
            dfs(s + "(",left - 1,right);
        }
        if (right > 0) {
            dfs(s + ")",left,right - 1);
        }
    }
}
